import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 46. 全排列
 * <a href="https://leetcode.cn/problems/permutations/">...</a>
 * User: DELL
 * Date: 2023-07-15
 * Time: 23:01
 */
public class Solution {
    /**
     * 简单的 dfs+回溯,遍历所有可能情况
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        // 题目保证输入合法,因此不需要做合法性检验
        List<List<Integer>> res = new ArrayList<>();
        boolean[] flags = new boolean[nums.length];
        Deque<Integer> stack = new LinkedList<>();
        dfs(res,nums,flags,stack);
        return res;
    }

    private void dfs(List<List<Integer>> res, int[] nums , boolean[] flags, Deque<Integer> stack) {
        if (stack.size() == nums.length) {
            res.add(new ArrayList<>(stack));
        }
        for (int i = 0; i < nums.length; i++) {
            if (!flags[i]) {
                flags[i] = true;
                stack.push(nums[i]);
                dfs(res,nums,flags,stack);
                flags[i] = false;
                stack.pop();
            }
        }
    }
}
